package 分治.归并排序;

// 可以用归并： 左半部分挑完-> 左排序->右边部分挑完-》右排序->
// 然后左右对比从最小的比，如果左不最小的还小就跳到下一个数
public class 数组中的逆序对51 {

    int [] arr1;
    int [] arr2;
  int [] tmp;
    int result = 0;
    public  int reversePairs(int[] nums) {

            int n = nums.length;
            tmp = new int[n];

            return mergeSort(nums,0,n-1);
    }
    public  int mergeSort(int[] nums, int left, int right) {
            if(left>= right) return 0;
            int  ret = 0;
            //1.选择一个中间点，将数组划分为两部分
            int mid = (left+right)/2;
            //[left,mid] [mid+1,right]

            //2.左半部分的个数+排序+右半部分的个数+排序
            ret +=mergeSort(nums,left,mid);
            ret +=mergeSort(nums,mid+1,right);

            // 3.一左一右的个数
            int cur1 = left, cur2 = mid+1,i = 0;
            while(cur1<= mid && cur2<=right)
            {
                if(nums[cur1]<=nums[cur2])
                {
                    tmp[i++] = nums[cur1++];
                }
                else
                {
                    ret +=mid-cur1+1;
                    tmp[i++] = nums[cur2++];
                }
            }
            //4.处理排序
            while(cur1<=mid) tmp[i++] = nums[cur1++];
            while (cur2<=right) tmp[i++] = nums[cur2++];

            for(int j =left;j<=right;j++)
                nums[j] = tmp[j-left];


            return ret;
    }

    public static void main(String[] args) {
        int[] nums={9,4,5,1,2,8};


    }

}
